package cn.xkai.general;

import java.util.ArrayList;
import java.util.List;

/**
 * @description: A星寻路算法
 * @author: kaixiang
 * @date: 2022/7/5
 **/
public class AStart {
    public static final int[][] MAZE = {
            {0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 1, 0, 0, 0},
            {0, 0, 0, 1, 0, 0, 0},
            {0, 0, 0, 1, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0}};

    public static Grid aStarSearch(Grid start, Grid end) {
        ArrayList<Grid> openList = new ArrayList<>();
        ArrayList<Grid> closeList = new ArrayList<>();
        openList.add(start);
        while (openList.size() > 0) {
            Grid currentGrid = findMinGrid(openList);
            openList.remove(currentGrid);
            closeList.add(currentGrid);
            List<Grid> neighbors = findNeighbors(currentGrid, openList, closeList);
            for (Grid grid : neighbors) {
                if (!openList.contains(grid)) {
                    grid.initGrid(currentGrid, end);
                    openList.add(grid);
                }
            }
            for (Grid grid : openList) {
                if (grid.x == end.x && grid.y == end.y) {
                    return grid;
                }
            }
        }
        return null;
    }

    private static ArrayList<Grid> findNeighbors(Grid grid, List<Grid> openList, List<Grid> closedList) {
        ArrayList<Grid> grids = new ArrayList<>();
        if (isValidGrid(grid.x, grid.y - 1, openList, closedList)) {
            grids.add(new Grid(grid.x, grid.y - 1));
        }
        if (isValidGrid(grid.x, grid.y + 1, openList, closedList)) {
            grids.add(new Grid(grid.x, grid.y + 1));
        }
        if (isValidGrid(grid.x - 1, grid.y, openList, closedList)) {
            grids.add(new Grid(grid.x - 1, grid.y));
        }
        if (isValidGrid(grid.x + 1, grid.y, openList, closedList)) {
            grids.add(new Grid(grid.x + 1, grid.y));
        }
        return grids;
    }

    private static boolean isValidGrid(int x, int y, List<Grid> openList, List<Grid> closedList) {
        if (x < 0 || x >= MAZE.length || y < 0 || y >= MAZE[0].length) {
            return false;
        }
        if (MAZE[x][y] == 1) {
            return false;
        }
        if (containsGrid(openList, x, y)) {
            return false;
        }
        if (containsGrid(closedList, x, y)) {
            return false;
        }
        return true;
    }

    private static boolean containsGrid(List<Grid> grids, int x, int y) {
        for (Grid grid : grids) {
            if (grid.x == x && grid.y == y) {
                return true;
            }
        }
        return false;
    }

    private static Grid findMinGrid(ArrayList<Grid> openList) {
        Grid temp = openList.get(0);
        for (Grid grid : openList) {
            if (grid.f < temp.f) {
                temp = grid;
            }
        }
        return temp;
    }

    static class Grid {
        public int x;
        public int y;
        public int g;
        public int h;
        public int f;
        public Grid parent;

        public Grid(int x, int y) {
            this.x = x;
            this.y = y;

        }

        public void initGrid(Grid parent, Grid end) {
            this.parent = parent;
            if (parent != null) {
                this.g = parent.g + 1;
            } else {
                this.g = 1;
            }
            this.h = Math.abs(this.x - end.x) + Math.abs(this.y - end.y);
            this.f = this.g + this.h;
        }
    }

    public static void main(String[] args) {
        Grid startGrid = new Grid(2, 1);
        Grid endGrid = new Grid(1, 6);
        Grid resultGrid = aStarSearch(startGrid, endGrid);
        ArrayList<Grid> path = new ArrayList<>();
        while (resultGrid != null) {
            path.add(new Grid(resultGrid.x, resultGrid.y));
            resultGrid = resultGrid.parent;
        }
        for (int i = 0; i < MAZE.length; i++) {
            for (int j = 0; j < MAZE[i].length; j++) {
                if (containsGrid(path, i, j)) {
                    System.out.print("* ");
                } else {
                    System.out.print(MAZE[i][j] + " ");
                }
            }
            System.out.println();
        }

        System.out.println("===老韩解法===");
        findWay(MAZE, 2, 1);
        for (int[] cells : MAZE) {
            for (int cell : cells) {
                System.out.print(cell + " ");
            }
            System.out.println();
        }
    }

    /**
     * 老韩解法: 找到通路(非最短路线)
     *
     * @param grid
     * @param i
     * @param j
     * @return
     */
    private static boolean findWay(int[][] grid, int i, int j) {
        if (i >= grid.length || i < 0 || j < 0 || j >= grid[0].length) {
            return false;
        }
        // 终点退出
        if (grid[1][6] == 2) {
            return true;
        }
        if (grid[i][j] == 0) {
            grid[i][j] = 2;
            if (findWay(grid, i, j + 1)) {
                return true;
            }
            if (findWay(grid, i + 1, j)) {
                return true;
            }
            if (findWay(grid, i - 1, j)) {
                return true;
            }
            if (findWay(grid, i, j - 1)) {
                return true;
            }
            grid[i][j] = 3;
            return false;
        }
        return false;
    }
}
